The present invention relates to integrated circuit design, and more specifically to a data structure and method for routing interconnections between components of an integrated circuit.
An overview of a typical design process for integrated circuits is shown in the flow diagram of FIG. 1. The process can be generally divided into a front-end design phase and a back-end development phase. During the front-end phase, from a set of specifications, the engineer designs and develops a logical representation of the integrated circuit of interest in the form of a schematic, at step 10. The schematic is then entered on computer workstation from which a circuit netlist is generated, at step 12. The netlist defines the entire integrated circuit, including all components and interconnections. Alternatively, the integrated circuit information may be developed using hardware description language (HDL) and synthesis. With the aid of circuit simulation tools available on the workstation, the designer then simulates the functionality of the circuit, at step 14. The circuit simulation process may involve several iterations of design modifications and improvements until the circuit design is finalized.
The back-end development involves several steps during which a final circuit layout (physical description) is developed based on the schematic. During placement step 16, various building blocks (or cells) as defined by the finalized circuit schematic are placed within a predefined floor plan. For integrated circuits designed based on array or standard cell technology, the various circuit building blocks are typically predefined and made available in a cell library. Placement is followed by a routing step 18, during which interconnects between circuit elements are routed throughout the layout. Finally, the accuracy of the layout versus the schematic is verified at step 20, and if no errors or design rule violations are found at step 22, then the circuit layout information is used for the process of fabrication at step 24.
During placement step 106 a plurality of cells are selected from one or more cell libraries and the cell interconnects are determined. For example, groups of cells may be interconnected to functions as flip-flops, shift registers and the like. The routing of wires to interconnect the cells and achieve the aforementioned functions is performed during the routing step 18, typically referred to as conducting paths, wires or nets.
For more complex designs, often at least four distinct layers of conducting medium are made available for routing. These layers include a polysilicon layer and three metal layers (metal-1, metal-2, and metal-3). The polysilicon layer, metal-1, metal-2, and metal-3 are typically employed for vertical and/or horizontal routing. It is a common practice to route each net by using one or more of the distinct layers of conducting medium. One layer of an adjacent pair of layers of conducting medium is typically reserved for connections running along one direction, e.g., the xe2x80x9cxxe2x80x9d direction, referred to as a preferred wiring direction. The remaining layer of the pair has a preferred wiring direction, which is orthogonal to the xe2x80x9cxxe2x80x9d direction, i.e., the preferred wiring direction is in the xe2x80x9cyxe2x80x9d direction. Some of the layers, such as the metal layers, are exclusively used for interconnection of components. The polysilicon layer may have a dual role, such as forming the gates of transistors as well as for interconnection of components. Electrical connections between two nets on adjacent layers is implemented with a xe2x80x9cviaxe2x80x9d which is an etched or drilled hole in the substrate for allowing a conductive path to extend from one layer to another layer.
Conventional design methodologies typically use a two-step process for determining the final size and location of each conducting path during the routing step 18. The first step is the global routing step for roughly determining conducting paths. The xe2x80x9croughxe2x80x9d wiring pattern generated in this step is known as a xe2x80x9cglobal route.xe2x80x9d Subsequently, a second detailed routing step for precisely determining a final routing pattern according to the global routes is used. This final routing pattern determined by the detailed routing step is known as a xe2x80x9cdetailed route.xe2x80x9d It is important to entertain certain constraints when routing an integrated circuit. These constraints are arranged in two categories: electrical rules and design rules. Electrical rules concern electrical performance parameters that must be satisfied by the conducting paths, e.g., cross-talk, circuit parasitics and the like. Design rules concern physical parameters that must be satisfied by the conducting paths, e.g., minimum spacing between adjacent wires, minimum wire width and the like. Owing to ever decreasing size of the components on integrated circuits and the increasing complexity of the constraints, computer-aided design (CAD) has become indispensable.
As a result, several algorithms are currently employed to assist in routing nets employing CAD technology. Specifically, the integrated circuit of interest is mapped into a memory of the CAD system. The algorithm searches the information in the memory concerning the integrated circuit in order to define a conductive path between two or more points. The maze algorithm is one of the most widely used algorithms for routing nets due to its superior searching capability. The searching capability afforded by the maze algorithm enables determination of the shortest distance required for net routing. Specifically, the maze algorithm commences at a starting location and expands outwardly therefrom to neighboring locations until the destination is reached, in order to identify a preferring conducting path. However, the processing time of the maze algorithm is long, on the order of a few days to several weeks.
Other algorithms have been employed to reduce the search time for a conducting path between two points. To that end, algorithms such as a hierarchical algorithm, a line search algorithm and a channel router algorithm have been developed. While each of these algorithms reduces the time required to route wires. The drawbacks differ.
To assist in search of a conducting path, the integrated circuit may be mapped into locations of a memory of the CAD system as an imaginary grid of points, referred to as a gridded data structure. The points may be stored as a sparse matrix, i.e., as line intervals in a preferred direction. The grid, or sparse matrix, is employed by the CAD system to route and track the location of the various conducting paths and components that make up the integrated circuit. To that end, status information is stored at each of the data points. The status information includes various attributes, such as data point state information: information concerning the availability of data point to receive a wire, i.e., open, or open with high cost, invalid or blocked. Additional information concerns the data point location in x, y and z coordinates; the net identifier, i.e., which net the data point is associated, the shapedef, the geometric shape of the wire present, as well as the allowed shapeclass and current conducting path cost.
Another technique maps the wiring plane of an integrated circuit into locations of a CAD system memory as a plurality of longitudinal tiles, referred to as a tiled data structure. Electrical components present in the wiring plane, as well as other blockages, are represented as polygonal objects. The tiled data structure requires much less memory to map the integrated circuit, compared to the gridded data structure. However, conducting path searches of the tiled data structure by the various algorithms are slower than the conducting path searches of the gridded data structure.
What is need, therefore, is a technique for routing wires for integrated circuits that is memory efficient.
Provided is a data structure containing wiring information for an integrated circuit and a method for storing the same in a computer readable medium. In one embodiment of the present invention storage of the data structure is achieved by mapping the integrated circuit into memory locations of the medium as a wiring plane having a plurality of data points arranged in a grid. Each of the plurality of data points has state information associated therewith that includes a plurality of attributes. Subsections of the grid are associated with memory locations in the computer readable medium to form a plurality of tiles. Specifically, the tiles and data points are arranged so that a sub-portion of the data points associated with one of the plurality of tiles have common attributes. In this manner, the common attributes need not be recorded for each data point in a given tile. Rather, the common attributes need only be stored once for each tile. Each data point may be associated with the common attribute, thereby reducing amount of information required to map the integrated circuit into the memory.
This is achieved by reducing the periodicity of the plurality of data points so that a distance between adjacent data points is less than a minimum wiring pitch defined by the design rules. For purposes of the present invention minimum wiring pitch is defined as being the sum of the minimum spacing between adjacent wires and the minimum width of a wire, both of which are measured transversely to a longitudinal axis of the wire. The width of the tiles is selected to be approximately equal to the minimum wiring pitch. As a result the attributes of adjacent data points in a common tile are closely related, if not identical. In an exemplary embodiment, the periodicity of the plurality of data points is selected so that a distance between adjacent data points is less than one half of a minimum wiring pitch. This results in no more than two values for each of the pride points being present in a common tile for the following attributes: shape definition, net identifier and shape classes.